package com.zzy.algorithm.tree;

import com.zzy.algorithm.model.TreeNode;

/**
 * LeetCode - 110 : 平衡二叉树
 *
 * 给定一个二叉树，判断它是否是高度平衡的二叉树。
 *
 * 本题中，一棵高度平衡二叉树定义为：
 *
 * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。
 *
 */
public class Q23_BalancedBinaryTree {

    public static void main(String[] args) {
        Q23_BalancedBinaryTree q23_balancedBinaryTree = new Q23_BalancedBinaryTree();
        int solution = q23_balancedBinaryTree.solution(TreeNode.treeNode1);
        System.out.println("solution = " + (solution != -1));
    }

    private int solution(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = solution(root.left);
        int right = solution(root.right);
        if(left == -1 || right == -1 || Math.abs(left - right) > 1){
            return -1;
        }
        return Math.max(left,right) + 1;
    }

}
